import java.util.*;

public class Main {
    /*
    public static void main1(String[] args) {
        int[] in = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int ret = 0;
        for (int i = 1900; i <= 9999; i++) {
            for (int j = 1; j <= 12; j++) {
                int day = in[j];
                if (j == 2 && (i % 4 == 0 && i % 100 != 0) || i % 400 == 0) day++;
                for (int k = 1; k <= day; k++) {
                    int year = i;
                    int n1 = 0;
                    int n2 = j / 10 + j & 10 + k / 10 + k % 10;
                    while (year > 0) {
                        n1 += year % 10;
                        year /= 10;
                    }
                    if (n1 == n2) ret++;
                }
            }
        }
        System.out.println(ret);
    }

    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int ret = 0;
        int n = 1;
        for (int i = 0; i < b; i++) {
            n *= a;
        }
        int m = (int) Math.sqrt(n);
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i < m; i++) {
            if (n % i == 0) list.add(i);
        }
        for (int i = 1; i < n; i++) {
            boolean flag = false;
            for (int j : list) {
                if (i % j == 0) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                ret++;
                ret %= 998244353;
            }
        }
        System.out.println(ret);
        scan.close();
    }

    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] in = new int[n][3];
        int[][] price = new int[n - 1][2];
        for (int i = 0; i < n; i++) {
            in[i][0] = scan.nextInt();
            in[i][1] = scan.nextInt();
            in[i][2] = scan.nextInt();
            if (i < n - 1) {
                price[i][0] = in[i][1];
                price[i][1] = in[i][2];
            }
        }
        Arrays.sort(price, (a, b) -> a[0] - b[0]);
        int ret = 0;
        for (int i = 0; i + 1 < n; i++) {
            m -= in[i][0];
            if (in[i + 1][0] > m) {
                for (int j = 0; j < in[i][2]; j++) {
                    ret += in[i][1];
                    in[j][1]--;
                    m++;
                }
                if (in[i + 1][0] > m) {
                    for (int k = 0; k < n; k++) {
                        while (price[k][1]-- > 0) {
                            ret += price[k][0];
                            m++;
                        }
                    }
                }
            }
        }
        System.out.println(ret);
        scan.close();
    }

    public static void main4(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x = scan.nextInt();
        int y = scan.nextInt();
        int[][] in = new int[n][3];
        for (int i = 0; i < 3; i++) {
            in[i][0] = scan.nextInt();
            in[i][1] = scan.nextInt();
            in[i][2] = scan.nextInt();
        }
        Arrays.sort(in, (a, b) -> {
            if (a[1] == b[1]) return a[0] - b[0];
            else return b[1] - a[1];
        });
        int left = in[0][0];
        int right = in[0][2] + left;
        int ret = 1;
        for (int i = 1; i < n; i++) {
            int a = in[i][0];
            int b = in[i][2] + a;
            if (right >= b && a < left) {
                ret++;
                left = a;
            } else if (a >= left && b > right) {
                ret++;
                right = b;
            } else if (a < left && b > right) {
                ret++;
                right = b;
                left = a;
            }
        }
        System.out.println(ret);
        scan.close();
    }

    public static void main22(String[] args) {
        long n = 1;
        long ret = 0;
        for (long i = 1; i <= 3; i++) {
            n *= 2023;
            n %= (1000000000 + 7);
        }
        for (long i = 1; i <= n; i++) {
            if (i % 2023 != 0) ret++;
            ret %= (1000000000 + 7);
        }
        System.out.println(ret);
        System.out.println(n);
        System.out.println(n - ret);
    }

    public static void main5(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] in = new int[2 * n];
        for (int i = 0; i < 2 * n; i++) in[i] = scan.nextInt();
        Arrays.sort(in);
        int ret = 0;
        int left = 0, right = 2 * n - 1;
        while (left < right) {
            ret += in[left++] * in[right--];
        }
        System.out.println(ret);
        scan.close();
    }

    public static boolean fun(int a, int b, int c, char op) {
        if (op == '+') {
            return a + b == c;
        } else if (op == '-') {
            return a - b == c;
        } else if (op == '*') {
            return a * b == c;
        } else {
            return a / b == c;
        }
    }

    public static void main7(String[] args) {
        Scanner scan = new Scanner(System.in);
        char[] ch = scan.next().toCharArray();
        int a = 0, b = 0, c = 0;
        char op = ' ';
        int i = 0;
        if (ch[i] != '?')
            while (ch[i] >= '0' && ch[i] <= '9') {
                a = a * 10 + (ch[i++] - '0');
            }
        else {
            a = -1;
            i++;
        }
        if (ch[i] == '+' || ch[i] == '-' || ch[i] == '*' || ch[i] == '/') op = ch[i];
        else op = '?';
        i++;
        if (ch[i] != '?')
            while (ch[i] >= '0' && ch[i] <= '9') {
                b = b * 10 + (ch[i++] - '0');
            }
        else {
            b = -1;
            i++;
        }
        i++;
        if (ch[i] != '?')
            while (i < ch.length && ch[i] >= '0' && ch[i] <= '9') {
                c = c * 10 + (ch[i++] - '0');
            }
        else {
            c = -1;
            i++;
        }
        if (a == -1) {
            a = 1;
            while (true) {
                if (fun(a, b, c, op)) break;
                a++;
            }
            System.out.println(a);
        } else if (b == -1) {
            b = 1;
            while (true) {
                if (fun(a, b, c, op)) break;
                b++;
            }
            System.out.println(b);
        } else if (c == -1) {
            c = 1;
            while (true) {
                if (fun(a, b, c, op)) break;
                c++;
            }
            System.out.println(c);
        } else {
            if (a + b == c)
                System.out.println('+');
            else if (a - b == c)
                System.out.println('-');
            else if (a * b == c)
                System.out.println('*');
            else if (a / b == c)
                System.out.println('/');
        }
        scan.close();
    }

    public static void main8(String[] args) {
        double s = 6.000;
        Integer[] in = {4, 3, 2, 1};
        Arrays.sort(in, (i, j) -> {
            return i % 2 - j % 2;
        });
        int left = 0, right = in.length - 1;
        while (left < right) {
            int mid = (right + left) / 2;
            if (in[mid] % 2 == 0) left = mid + 1;
            else right = mid;
        }
        System.out.println(in[right]);
        //System.out.printf("%.2f",s);
    }

    public static void main9(String[] args) {
        Scanner scan = new Scanner(System.in);
        double ret = 0;
        int n = scan.nextInt();
        int[] in = new int[n];
        int[][] arr = new int[n - 1][2];
        for (int i = 0; i < n; i++) {
            in[i] = scan.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            arr[i][0] = scan.nextInt();
            arr[i][1] = scan.nextInt();
        }
        ret += in[0];
        int index = 0;
        int high = 0;
        for (int[] t : arr) {
            if (high < t[1]) {
                ret += (t[1] - high) / 0.7;
                high = t[1];
            } else if (high > t[1]) {
                ret += (high - t[1]) / 1.3;
                high = t[1];
            }
        }
        ret += high / 1.3 + in[n] - in[n - 1];
        System.out.printf("%.2f", ret);
        scan.close();
    }

    public static void main11(String[] args) {
        System.out.println(fun(126, Integer.toString(126, 16)));
    }

    public static boolean fun(int n, String s) {
        int sum = 0;
        int[] in = new int[s.length()];
        int i = 0;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9')
                in[i++] = c - '0';
            else
                in[i++] = c - 'a' + 10;
        }
        i = 0;
        while (i < s.length()) {
            sum += in[i++];
        }
        if (n % sum == 0) return true;
        return false;
    }

    public static void main55(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] in = new int[n];
        long ret = 0;
        for (int i = 0; i < n; i++) in[i] = scan.nextInt();
        Arrays.sort(in);
        PriorityQueue<Integer> q1 = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> q2 = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0; i < n / 2; i++) {
            q2.add(in[i]);
        }
        for (int i = n / 2; i < n; i++) {
            q1.add(in[i]);
        }
        while (q2.size() > 0 && q1.size() > 1) {
            int n1 = q1.poll();
            int n2 = q1.poll();
            if (q2.size() > 0 && n2 / 2 >= q2.peek()) {
                q2.poll();
            } else if (q2.size() > 0 && n2 / 2 < q2.peek()) {
                while (q2.size() > 0 && n2 / 2 < q2.peek()) {
                    q1.add(q2.poll());
                }
                if (q2.size() > 0 && n2 / 2 >= q2.peek())
                    q2.poll();
            }
            ret += n1 + n2;
            while (q2.size() > 0 && q1.size() < 2) q1.add(q2.poll());
        }
        for (int x : q1) ret += x;
        System.out.println(ret);
        scan.close();
    }

    public static void main223(String[] args) {
        Scanner scan = new Scanner(System.in);
        PriorityQueue<Integer> q0 = new PriorityQueue<>();
        PriorityQueue<Integer> q2 = new PriorityQueue<>();
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        long ret = 0;
        int n = scan.nextInt();
        int[] count = new int[n];
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) count[i] = scan.nextInt();
        for (int i = 0; i < n; i++) nums[i] = scan.nextInt();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) q0.add(count[i]);
            else if (nums[i] == 1) q1.add(count[i]);
            else q2.add(count[i]);
        }
        while (q0.size() > 1 || q1.size() > 1 || q2.size() > 1) {
            int num = fun(q0, q1, q2);
            if (num == 0 && q0.size() > 1) {
                int sum = q0.poll() + q0.poll();
                ret += sum;
                q1.add(sum);
            } else if (num == 1 && q1.size() > 1) {
                int sum = q1.poll() + q1.poll();
                ret += sum;
                q2.add(sum);
            } else if (num == 2 && q2.size() > 1) {
                int sum = q2.poll() + q2.poll();
                ret += sum;
                q0.add(sum);
            }
        }
        System.out.println(ret);
        scan.close();
    }

    public static int fun(PriorityQueue<Integer> q0, PriorityQueue<Integer> q1, PriorityQueue<Integer> q2) {
        int num1 = 0, num2 = 0, num0 = 0;
        if (q1.size() > 1) num1 = q1.peek();
        if (q2.size() > 1) num2 = q2.peek();
        if (q0.size() > 1) num0 = q0.peek();
        if (num0 == 0 && num1 == 0) return 2;
        if (num1 == 0 && num2 == 0) return 0;
        if (num2 == 0 && num0 == 0) return 1;
        if (num1 == 0) {
            return num0 > num2 ? 2 : 0;
        }
        if (num2 == 0) {
            return num1 > num0 ? 0 : 1;
        }
        if (num0 == 0) {
            return num1 > num2 ? 2 : 1;
        }
        if (num1 <= num2 && num1 <= num0) return 1;
        if (num0 <= num2 && num0 <= num2) return 0;
        if (num2 <= num1 && num2 <= num0) return 2;
        return -1;
    }

    public static void main221(String[] args) {
        long mod = 1000000007;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            int odd = 0, even = 0;
            int count = scan.nextInt();
            for (int j = 0; j < count; j++) {
                if (scan.nextInt() % 2 == 0) odd++;
                else even++;
            }
            if (even % 2 == 0) {
                ret[i] = (int) (Math.pow(2, odd) * Math.pow(2, even > 0 ? even - 1 : 0) % mod);
            }
            System.out.println(ret[i]);
        }
        scan.close();
    }

    public static void mai3n(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] in = new int[n];
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            in[i] = scan.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            a[i] = scan.nextInt();
            b[i + 1] = scan.nextInt();
        }
        double[] f = new double[n];
        double[] g = new double[n];
        double ret = 0;
        f[0] = in[0];
        g[0] = in[0] + a[0] / 0.7;
        for (int i = 1; i < n; i++) {
            f[i] = Math.min(g[i - 1] + b[i] / 1.3, f[i - 1] + in[i]);
            g[i] = Math.min(f[i - 1] + a[i] / 0.7, g[i - 1] + b[i] > a[i] ? b[i] - a[i] / 1.3 : a[i] - b[i] / 0.7);
            ret = Math.min(f[i], g[i]);
        }
        System.out.printf("%.2f", ret);
        scan.close();
    }

    public static void main112(String[] args) {
        long ret = 0;
        long n = 1;
        int i = 1;
        while (true) {
            n *= i;
            if (n % 1000000000L == 0) break;
            n %= 1000000000L;
            ret += n;
            i++;
        }
        System.out.println(ret % 1000000000L);
        System.out.println(i);
    }

    public static void main1231(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<List<Integer>> l = new ArrayList<>();
        for (int i = 0; i < n; i++) l.add(new ArrayList<>());
        int index = 0;
        while (scan.hasNext()) {
            String str = scan.next();
            if (str.equals("add")) {
                int num = scan.nextInt();
                l.get(0).add(num);
            } else if (str.equals("sync")) {
                int num = scan.nextInt();
                int len = l.get(num).size();
                if (len == l.get(0).size()) continue;
                int a = l.get(0).get(len);
                l.get(num).add(a);
            } else {
                int a = l.get(1).size();
                for (int i = 2; i < n; i++) {
                    a = Math.min(a, l.get(i).size());
                }
                System.out.println(a);
            }
        }
        scan.close();
    }

    public static void main12(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for (int i = 0; i < n; i++) {
            long ret = 0;
            int[] in = new int[5];
            for (int j = 0; j < 5; j++) {
                in[j] = scan.nextInt();
            }
            while (in[4]-- > 0) {
                if (in[2]-- > 0 && in[0]-- > 0) {
                    ret += 6;
                } else if (in[1] > 1) {
                    ret += 6;
                    in[1] -= 2;
                } else if (in[0] > 2) {
                    ret += 6;
                    in[0] -= 3;
                } else {
                    if (in[2]-- > 0) ret += 4;
                    else if (in[1]-- > 0 && in[0]-- > 0) ret += 5;
                    else if (in[1]-- > 0) ret += 3;
                    else if (in[0]-- > 0) ret += 2;
                    break;
                }
            }
            while (in[3]-- > 0) {
                if (in[2]-- > 0) ret += 4;
                else if (in[1]-- > 0) ret += 3;
                else if (in[0] > 0) {
                    if (in[0] > 1) {
                        in[0] -= 2;
                        ret += 4;
                    } else {
                        in[0]--;
                        ret += 2;
                    }
                }
            }
            System.out.println(ret);
        }
        scan.close();
    }

    public static void main532(String[] args) {
        //int l = 10000000 - 1;
        int l = 7913837;
        while (l > 0) {
            if (dfs(l)) {
                System.out.println(l);
                break;
            }
            l--;
        }
    }

    public static boolean dfs(int n) {
        int _n = n;
        List<Integer> l = new ArrayList<>();
        int count = 0;
        while (_n > 0) {
            l.add(_n % 10);
            _n /= 10;
            count++;
        }
        Collections.reverse(l);
        int sum = 0;
        for (int i = 0; i < count; i++) {
            sum += l.get(i);
        }
        l.add(sum);
        while (sum < n) {
            sum += sum;
            sum -= l.get(l.size() - count - 1);
            l.add(sum);
        }
        if (sum == n) return true;
        return false;
    }

    public static void main221431(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        double p = scan.nextDouble();
        int ret = 1;
        double min = n * 1.0;
        for (int k = 1; k <= n; k++) {
            if (n % k == 0) {
                //double num = n * (1 - Math.pow(1 - p,k)) + n / k;
                double num = n / k * (Math.pow(1 - p, k) + (1 - Math.pow(1 - p, k)) * (k + 1));
                if (num < min) {
                    min = num;
                    ret = k;
                }
            }
        }
        System.out.println(ret);
        scan.close();
    }

    public static void main165(String[] args) {
        Scanner sc = new Scanner(System.in);
        long K = sc.nextLong(); //K必须是long类型，不然会报段错误
        long l = 1l; //l在最左边
        long r = Long.MAX_VALUE - 1; //r在最右边
        while (l < r) {
            long mid = (l + r) / 2; //二分法
            if (K <= calc(mid)) {
                r = mid; //r为阶乘的末尾
            } else {
                l = mid + 1; //左指针右移
            }
        }
        if (calc(r) != K) { //如果遍历完毕最后求r阶乘末尾的0个数不等于K的话就返回-1
            System.out.println(-1);
        } else {
            System.out.println(r); //找到r 输出
        }
        sc.close();
    }

    static long calc(long x) {
        long res = 0;
        //求阶乘末尾0的个数其实就是 求阶乘因子中5的个数
        //5！= 1 * 2 * 3 * 4 * 5 = 120
        //10！ = 1 * 2 * 3 * 4 * 5 * ... * 9 * 2 * 5 = 3628800
        //15！= 1 * 2 * 3 * 4 * 5 * ... * 9 * 2 * 5 * ... * 14 * 3 * 5 = 1307674368000
        while (x != 0) {
            res = res + x / 5; //求5的个数，如果x为17时，while()循环没有结束，这里不用担心x取到17
            x /= 5;
        }
        return res;
    }

    public static void main54654(String[] args) {
        int mod = 1000000007;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] in = new int[n + 1];
        for (int i = 1; i <= n; i++) in[i] = scan.nextInt();
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[0] = 1;
        for (int i = 2; i <= n; i++) {
            int max = in[i];
            int min = in[i];
            for (int j = i; j >= 1; j--) {
                int len = i - j;
                max = Math.max(max, in[j]);
                min = Math.min(min, in[j]);
                if (max - min == len) {
                    dp[i] = ((dp[i] % mod) + (dp[j - 1] % mod)) % mod;
                }
            }
        }
        System.out.println(dp[n] % mod);
        scan.close();
    }

    public static void main415(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        // 额外添加一个特殊的公司节点
        int m = sc.nextInt() + 1;
        int k = sc.nextInt();
        long v = sc.nextInt();
        long[] a = new long[m + 1], b = new long[m + 1], c = new long[m + 1];
        for (int i = 1; i <= m - 1; i++) {
            // 将所有距离乘v就可以当做单位1来计算
            a[i] = sc.nextInt() * v;
            b[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }
        // 为公司定义一个特殊的红绿灯时间
        a[m] = n * v;
        b[m] = 1;
        c[m] = 0;

        // 以下dp状态均表示等完i路口红绿灯后的时间
        // dp[i][0] 表示从i-1号节点开车过来
        // dp[i][1] 表示从i-1号节点闪现过来
        long[][] dp = new long[m + 1][2];
        for (int i = 1; i <= m; i++) {
            long s1 = a[i] - a[i - 1];
            long time1 = calc(dp[i - 1][0], s1, b[i], c[i]);
            long time2 = calc(dp[i - 1][1], s1, b[i], c[i]);
            // 从到达i-1节点的最短时间直接开车过来
            dp[i][0] = Math.min(time1, time2);

            // 从i-1节点闪现过来，要从i-k节点一直开车过来
            int po = Math.max(0, i - k);
            // 在位置po选一个最短的做起始时间time3
            long time3 = Math.min(dp[po][0], dp[po][1]);
            // 起点区间：[po, i-1]
            for (int j = po; j <= i - 1; j++) {
                long s = a[j + 1] - a[j];
                // 如果是i-1号路口，表示闪现，距离设置为0
                if (j == i - 1) {
                    s = 0;
                }
                time3 = calc(time3, s, b[i], c[i]);
            }
            dp[i][1] = time3;
        }
        System.out.print(Math.min(dp[m][0], dp[m][1]));
    }

    // 起始时间start，返回到达下一个路口等完红绿灯的时间
    public static long calc(long start, long s, long green, long red) {
        // res 初始化为到达路口的时间
        long res = start + s;
        long t = (start + s) % (green + red);
        // 根据消除多轮红绿灯组合的剩余时间，计算等红灯时间
        if (t >= green) {
            res += (green + red) - t;
        }
        return res;
    }

    public static void main5164156(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[] in = new long[n];
        long sum1 = 0, sum2 = 0;
        for (int i = 0; i < n; i++) {
            in[i] = scan.nextLong();
        }
        long ret = 0;
        for (int i = n - 1; i >= 1; i--) {
            for (int j = n - 1; j >= 1; j--) {
                sum1 ^= in[j];
                for (int k = 0; k < j; k++) {
                    for (int k1 = k; k1 <= k; k1++) {
                        sum2 ^= in[k1];
                        ret = Math.max(Math.abs(sum1 - sum2), ret);
                    }
                    sum2 ^= in[k];
                }
            }
            sum1 ^= in[i];
        }
        System.out.print(ret);
        scan.close();
    }

    static int N = 1010;

    public static void main4656458645(String[] args) {
        // TODO Auto-generated method stub
        //1.暴力解法，利用四层for循环，能解决70%
        //2.采用二维单调队列
        Scanner scan = new Scanner(System.in); //接受数据
        String str = scan.nextLine();
        String[] st = str.split(" ");
        int n = Integer.parseInt(st[0]);
        int m = Integer.parseInt(st[1]);
        int a = Integer.parseInt(st[2]);
        int b = Integer.parseInt(st[3]);
        int[][] mat = new int[n][m];
        int[][] resMin = new int[N][N];
        int[][] resMax = new int[N][N];
        int[] Min = new int[N];
        int[] Max = new int[N];
        int[] rea = new int[N];
        int[] reb = new int[N];
        for (int i = 0; i < n; i++) {
            String s = scan.nextLine();
            String[] sub = s.split(" ");
            for (int j = 0; j < m; j++) {
                mat[i][j] = Integer.parseInt(sub[j]);
            }
        }
        for (int i = 0; i < n; i++) {//对每一行利用单调队列求最大最小值
            getMin(mat[i], m, b, resMin[i]);
            getMax(mat[i], m, b, resMax[i]);
        }
        long res = 0;
        for (int i = b - 1; i < m; i++) {//列
            for (int j = 0; j < n; j++) {//行
                rea[j] = resMin[j][i];
                reb[j] = resMax[j][i];
            }
            getMin(rea, n, a, Min);//对每一列元素求最小值，即操作rea，即每一列的最小值
            getMax(reb, n, a, Max);
            for (int j = a - 1; j < n; j++) {
                res = (res + 1L * Max[j] * Min[j]) % 998244353;
            }
        }

        System.out.println(res);
    }

    public static void getMin(int[] arr, int m, int k, int[] resMin) {
        int[] que = new int[m];//单调队列
        int head = 0, tail = -1;
        for (int i = 0; i < m; i++) {//遍历每一行

            //最小值
            while (head <= tail && arr[que[tail]] >= arr[i]) tail--;
            que[++tail] = i;
            if (que[head] < i - k + 1) head++;
            resMin[i] = arr[que[head]];
        }
    }

    public static void getMax(int[] arr, int m, int k, int[] resMax) {//单调队列求最大值
        int[] que = new int[m];//单调队列
        int head = 0, tail = -1;
        for (int i = 0; i < m; i++) {//遍历每一行

            //最大值
            while (head <= tail && arr[que[tail]] <= arr[i]) tail--;
            que[++tail] = i;
            if (que[head] < i - k + 1) head++;
            resMax[i] = arr[que[head]];
        }
    }

    public static void main4124132(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int a = Integer.MAX_VALUE;
        int b = a;          //初始化答案为最大值
        for (int i = 1; i <= n; i++) {
            int x = scan.nextInt();   //读取一个数
            for (int j = 2; j * j <= x; j++) {   //求质因数
                if (x % j == 0) {
                    if (map.containsKey(j)) {   //如果之前存在这个质因数
                        if (map.get(j) < a) {       //如果它比目前的方法优
                            a = map.get(j);          //则将a,b都替换
                            b = i;
                        } else if (map.get(j) == a) { //如果它们相等，则只要
                            if (i < b) b = i;            //判断b是否需要优化
                        }
                    } else
                        map.put(j, i);              //之前没出现过则存入
                    while (x % j == 0) x /= j;         //emmm,如果是16，则
                }                            //到2应该一直除到1
            }
            if (x > 1) {            //如果剩下的数大于1，则它也是个质因数
                if (map.containsKey(x)) {    //重复刚刚上面的判断
                    if (map.get(x) < a) {
                        a = map.get(x);
                        b = i;
                    } else if (map.get(x) == a) {
                        if (i < b) b = i;
                    }
                }
                map.put(x, i);
            }
        }
        System.out.print(a + " " + b);
        scan.close();
    }

    public static void main6541(String[] args) {
        int mod = 100000000;
        int n = 4;
        int x = 6;
        int res = 1;
        while (n > 0) {
            if (n % 2 == 1) res = res * x % mod;
            x = x * x % mod;
            n /= 2;
        }
        System.out.println(res);
    }
    public static void main4658(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int s = scan.nextInt();
        int[] p = new int[n];
        int[] c = new int[n];
        int sum = 0;
        int ret = 0;
        Integer[] in = new Integer[n];
        for(int i = 0;i < n;i++){
            p[i] = scan.nextInt();
            c[i] = scan.nextInt();
            in[i] = i;
            sum += p[i];
        }
        Arrays.sort(in,(i,j)->{
            if(c[i] == c[j])return p[i] - p[j];
            else return c[i] - c[j];
        });
        int left = 0,right = n - 1,count = 0;
        while(sum > s){
            ret += s;
            count++;
            //for(int i = left;i <= right;i++)c[in[i]]--;
            //while(c[in[left]] == 0){
            while(c[in[left]] - count == 0){
                sum -= p[in[left]];
                left++;
            }
        }
        for(int i = 0;i < n;i++){
            if(c[in[i]] - count != 0){
                ret += c[in[i]] * p[in[i]];
            }
        }
        System.out.print(ret);
        scan.close();
    }
    public static void main4156651(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[] in = new long[n];
        for(int i = 0;i < n;i++){
            in[i] = scan.nextLong();
        }
        long[] nums = new long[n/2];
        for(int i = 0;i < n / 2;i++){
            nums[i] = in[i] - in[n-1-i];
        }
        int ret = 0;
        int i = 0;
        while(true){
            if(nums[i] == 0)i++;
            if(nums[i] > 0){
                if(i + 1 < n / 2 && nums[i+1] > 0){
                    nums[i+1]--;
                }
                nums[i]--;
                ret++;
            }else if (nums[i] < 0){
                if(i + 1 < n / 2 && nums[i+1] < 0){
                    nums[i+1]++;
                }
                nums[i]++;
                ret++;
            }
            if(i == n / 2 - 1 && nums[i] == 0)break;
        }
        System.out.print(ret);
        scan.close();
    }
        public static int[] in;
        public static int[] dx = {1,-1};
        public static boolean[] vis;
        public static int ret,n,m;
        public static void main5545634154163(String[] args) {
            Scanner scan = new Scanner(System.in);
            n = scan.nextInt();
            m = scan.nextInt();
            in = new int[n];
            vis = new boolean[n];
            for(int i = 0;i < n;i++)in[i] = scan.nextInt();
            Arrays.sort(in);
            for(int i = 0;i < n;i++){
                if(Math.abs(0 - in[i]) <= m){
                    vis[i] = true;
                    dfs(i,m - Math.abs(0 - in[i]),1);
                    vis[i] = false;
                }
            }
            System.out.print(ret);
            scan.close();
        }
        public static void dfs(int i,int count,int sum){
            ret = Math.max(ret,sum);
            for(int k = 0;k < 2;k++){
                int x = dx[k] + i;
                if(x >= 0 && x < n && count - Math.abs(in[x] - in[i]) >= 0){
                    if(!vis[x]) {
                        sum++;
                        vis[x] = true;
                    }
                    dfs(x,count - Math.abs(in[x] - in[i]),sum);
                    if(!vis[x]) {
                        sum++;
                        vis[x] = true;
                    }
                }
            }
        }

    public static void main45(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        int mx = (int)1e6 + 10;
        int[] a = new int[n + 5];
        int[] t = new int[4*mx+10];
        for(int i = 1; i <= n; i++) {
            a[i] = scan.nextInt();
            a[i] += mx;
            t[a[i]]++;
        }
        for(int i = 1; i <= mx * 4; i++) t[i] += t[i - 1];
        int res = 0;
        for(int i = mx; i >= mx - 1e6; i--) {
            int r = m - (mx - i) * 2 + mx;
            res = Math.max(res, t[Math.max(i, r)] - t[i - 1]);
        }
        for(int i = mx; i <= mx + 1e6; i++) {
            int l = mx - m + (i - mx) * 2;
            res = Math.max(res, t[i] - t[Math.max(0, l - 1)]);
        }
        System.out.println(res);
    }
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        int[] days = {0,31,28,31,30,31,30,31,31,30,31,30,31};
//        int[] year = {41,29,30,31,33};
//        int[] in = {0,14,15,16,18,17,17,15,15,15,14,2,3,4,6,5,5,3,3,3,15,3,4,5,7,6,6,4,4,4,16,4};
//        int ret = 0;
//        for(int i = 2000;i <= 2024;i++){
//            for(int j = 1;j <= (i == 2024 ? 4 : 12);j++){
//                int day = days[j];
//                if(j == 2 && ((i % 4 == 0 && i % 100 != 0) || i % 400 == 0)){
//                    day++;
//                }
//                for(int k = 1;k <= day;k++){
//                    if(year[i - 2000] + in[j] + in[k] > 50)ret++;
//                }
//            }
//        }
//        System.out.print(ret);
//        scan.close();
//    }
    public static void main645645(String[] args) {
        long n = 2;
        long k = 42;
        long ret = 1;
        while(k > 0){
            if(k % 2 == 1)ret *= n;
            n *= n;
            k /= 2;
        }
        System.out.println(ret);
    }
 */
/*    public static int[] dx = {0,1,1,1,0,-1,-1,-1};
    public static int[] dy = {-1,-1,0,1,1,1,0,-1};
    public static boolean[][] vis;
    public static int[][] in;
    public static int n,k;
    public static StringBuilder ret;
    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        in = new int[n][n];
        ret = new StringBuilder();
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)in[i][j] = scan.nextInt();
        vis = new boolean[n][n];
        vis[0][0] = true;
        dfs(0,0,1,in[0][0]);
        System.out.print(ret.length() < (n*n-1) ? -1 : ret.reverse().toString());
        scan.close();
    }
    public static boolean dfs(int i,int j,int count,int num){
        if(num == k - 1)num = -1;
        if(count == n*n){
            if(i == n - 1 && j == n - 1)return true;
            return false;
        }
        for(int k = 0;k < 8;k++){
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < n && y >= 0 && y < n && !vis[y][x] && in[y][x] == num + 1){
                vis[y][x] = true;
                if(dfs(x,y,count+1,num+1)){
                    ret.append(k);
                    return true;
                }
                vis[y][x] = false;
            }
        }
        return false;
    }*/


    //    public static int[] dx = {0,1,1,1,0,-1,-1,-1};
//    public static int[] dy = {-1,-1,0,1,1,1,0,-1};
//    public static boolean[][] vis;
//    public static int[][] in;
//    public static int n,k;
//    public static StringBuilder ret;
//    public static List<String> list;
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        n = scan.nextInt();
//        k = scan.nextInt();
//        in = new int[n][n];
//        ret = new StringBuilder();
//        for(int i = 0;i < n;i++)
//            for(int j = 0;j < n;j++)in[i][j] = scan.nextInt();
//        vis = new boolean[n][n];
//        vis[0][0] = true;
//        list = new ArrayList<>();
//        dfs(0,0,1,in[0][0]);
//        if(list.size() > 0){
//            String num = list.get(0);
//            for(String str : list){
//                if(num.compareTo(str) > 0){
//                    num = str;
//                }
//            }
//            System.out.println(num);
//        }else System.out.println(-1);
//        scan.close();
//    }
//    public static void dfs(int i,int j,int count,int num){
//        if(num == k - 1)num = -1;
//        if(count == n*n){
//            if(i == n - 1 && j == n - 1){
//                list.add(ret.reverse().toString());
//            }
//        }
//        for(int k = 0;k < 8;k++){
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if(x >= 0 && x < n && y >= 0 && y < n && !vis[y][x] && in[y][x] == num + 1){
//                vis[y][x] = true;
//                ret.append(k);
//                dfs(x,y,count+1,num+1);
//                ret.delete(ret.length()-1,ret.length());
//                vis[y][x] = false;
//            }
//        }
//    }
//    public static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
//    public static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
//    public static boolean[][] vis;
//    public static int[][] in;
//    public static int n, k;
//    public static StringBuilder ret;
//
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        n = scan.nextInt();
//        k = scan.nextInt();
//        in = new int[n][n];
//        ret = new StringBuilder();
//        for (int i = 0; i < n; i++)
//            for (int j = 0; j < n; j++) in[i][j] = scan.nextInt();
//        vis = new boolean[n][n];
//        vis[0][0] = true;
//        dfs(0, 0, 1, in[0][0]);
//        System.out.print(ret.length() < (n * n - 1) ? -1 : ret.reverse().toString());
//        scan.close();
//    }
//
//    public static boolean dfs(int i, int j, int count, int num) {
//        if (num == k - 1) num = -1;
//        if (count == n * n) {
//            if (i == n - 1 && j == n - 1) return true;
//            return false;
//        }
//        for (int k = 0; k < 8; k++) {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < n && y >= 0 && y < n && !vis[y][x] && in[y][x] == num + 1) {
//                vis[y][x] = true;
//                if (dfs(x, y, count + 1, num + 1)) {
//                    ret.append(k);
//                    return true;
//                }
//                vis[y][x] = false;
//            }
//        }
//        return false;
//    }
//    public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
//    public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
//    public static boolean[][] vis;
//    public static boolean[][][][] ban;
//    public static int[][] in;
//    public static int n, k;
//    public static boolean flag;
//    public static int[] ret;
//
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        n = scan.nextInt();
//        k = scan.nextInt();
//        in = new int[n][n];
//        ret = new int[100];
//        for (int i = 0; i < n; i++)
//            for (int j = 0; j < n; j++) in[i][j] = scan.nextInt();
//        vis = new boolean[n][n];
//        ban = new boolean[n][n][n][n];
//        vis[0][0] = true;
//        dfs(0, 0, 0, in[0][0]);
//        if(!flag)System.out.print(-1);
//        scan.close();
//    }
//
//    public static void dfs(int i, int j, int count, int num) {
//        if (num == k - 1) num = -1;
//        if (count == n * n - 1) {
//            if (i == n - 1 && j == n - 1){
//                for(int a : ret){
//                    System.out.print(a);
//                }
//                flag = true;
//                return;
//            }
//        }
//        for (int k = 0; k < 8; k++) {
//            int x = dx[k] + i;
//            int y = dy[k] + j;
//            if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && in[x][y] == num + 1) {
//                vis[x][y] = true;
//                ban[x][y][i][j] = true;
//                ban[i][j][x][y] = true;
//                ret[count] = k;
//                if(k % 2 == 1){
//                    if(!ban[x][j][i][y])dfs(x,y,count + 1,num + 1);
//                }else dfs(x,y,count + 1,num + 1);
//                ban[x][y][i][j] = false;
//                ban[i][j][x][y] = false;
//                vis[x][y] = false;
//            }
//        }
//    }
    public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static boolean[][] vis;
    public static boolean[][][][] ban;
    public static int[][] in;
    public static int n, k;
    public static boolean flag;
    public static int[] ret;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        in = new int[n][n];
        ret = new int[n * n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) in[i][j] = scan.nextInt();
        vis = new boolean[n][n];
        ban = new boolean[n][n][n][n];
        vis[0][0] = true;
        dfs(0,0,0,in[0][0]);
        if(!flag)System.out.print(-1);
        scan.close();
    }

    public static void dfs(int i, int j, int count, int num) {
        if (num == k - 1) num = -1;
        if (count == n * n - 1) {
            if (i == n - 1 && j == n - 1){
                if(!flag)
                for(int k = 0;k < n * n - 1;k++){
                    System.out.print(ret[k]);
                }
                flag = true;
                return;
            }
        }
        for (int k = 0; k < 8; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && in[x][y] == num + 1) {
                vis[x][y] = true;
                ban[x][y][i][j] = true;
                ban[i][j][x][y] = true;
                ret[count] = k;
                if(k % 2 == 1){
                    if(!ban[x][j][i][y])dfs(x,y,count + 1,num + 1);
                }else dfs(x,y,count + 1,num + 1);
                ban[x][y][i][j] = false;
                ban[i][j][x][y] = false;
                vis[x][y] = false;
            }
        }
    }
}
